/**
 * 二叉树的深搜与广搜
 * 深度优先搜索：更适合探索未知
 * 广度优先搜索：更适合探索局域
 */


class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const a = new TreeNode("A");
const b = new TreeNode("B");
const c = new TreeNode("C");
const d = new TreeNode("D");
const e = new TreeNode("E");
const f = new TreeNode("F");
const g = new TreeNode("G");
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.left = f;
c.right = g;

/**
 * 深搜(深搜的顺序与前序遍历的顺序是一样的)
 * @param root 二叉树根节点
 * @param target 待查找元素
 */
function deepSearch(root, target) {
  if (!root) return false;
  if (root.val === target) return true;
  return deepSearch(root.left, target) || deepSearch(root.right, target);
}

console.log("▶『deepSearch』", deepSearch(a, "F"));

/**
 * 广搜(递归实现)
 * @param root 二叉树根节点
 * @param target 待查找元素
 */
function broadSearch1(roots, target) {
  if (roots == null || roots.length == 0) return false;
  let queue = [];
  for (let i = 0; i < roots.length; i++) {
    if (roots[i].val === target) {
      return true;
    } else {
      roots[i]?.left && queue.push(roots[i]?.left);
      roots[i]?.right && queue.push(roots[i]?.right);
    }
  }
  return broadSearch1(queue, target);
}

console.log("▶『broadSearch 递归』", broadSearch1([a], "G"));

/**
 * 广搜(非递归实现)
 * @param root 二叉树根节点
 * @param target 待查找元素
 */
function broadSearch2(root, target) {
  if (!root) return false;
  let queue = [root];
  while (queue.length) {
    let node = queue.shift();
    if (node.val === target) return true;
    node.left && queue.push(node.left);
    node.right && queue.push(node.right);
  }
  return false;
}

console.log("▶『broadSearch 非递归』", broadSearch2(a, "Z"));
